188. 买卖股票的最佳时机 IV

Similar Question

Solution Tips

方案一: 动态规划

var maxProfit = function(k, prices) {
    //  交易 k 次, 就有 k * 2 的状态
    const k2 = k * 2;
    // 参考 III, 定义出状态就行, 用一个 for 循环 k 取处理
    // 进阶的逻辑和背包问题很想
    const n = prices.length;
    // 没有股票, 持有股票, 卖出股票(没有股票)
    // 1. 可以交易 k 次, 就有 k * 2  种状态, 分别是第 k 次持有股票, 和第 k 次卖出股票
    // dp[i][j] 的定义就是, 在第 i 天的时候, 处于不同的状态 k 所持有的最大现金
    const dp = Array.from({ length: n }, () => Array.from({ length: k2 + 1 }));
    // 3. 初始化, 从状态转移公式来看, 需要初始化第 0 天的所有状态, 这样第 1 天才能参考
    for (let i = 0; i <= k2; i += 2) {
        // 第 i 次 不持有股票的状态
        dp[0][i] = 0;
    }
    for (let i = 1; i <= k2; i += 2) {
        // 第 i 次 持有股票的状态, 可以理解为在第 0 天就疯狂的买入卖出, 从而达到第 i / 2 次交易
        dp[0][i] = -prices[0];
    }
    for (let i = 1; i < n; i++) {
        // 每一天都不操作的话就一直是 0
        dp[i][0] = 0;
        for (let j = 1; j <= k2; j += 2) {
            // 持有的状态
            // 对于每一次持有来说 dp[i][k % 2 === 1]
            // 可以由前一天没有买入股票的价格而来, 今天买入, 从而达成持有状态 dp[i]k] = dp[i -1][k - 1] - prices[i]
            // 可以由前一天持有股票的状态而来, 今天继续持有即可
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
        }
        for (let j = 2; j <= k2; j += 2) {
            // 不持有股票的状态
            // 对于每一次持有来说 dp[i][k % 2 === 2]
            // 可以由前一天有买入股票的价格而来, 将股票卖出, 从而达成未持有状态 dp[i]k] = dp[i -1][k - 1] + prices[i]
            // 可以由前一天未持有股票的状态而来, 今天继续不持有
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
        }

    }

    // 金额最多的一定是卖出次数最多的, 可以获益最多
    return dp[n - 1][k2];
};